先来看一道模板题：P3810@洛谷 - 【模板】三维偏序（陌上花开）。
考虑 暴力枚举，但是数据范围大到离谱，因此这种方法显然行不通。
下面就来讲解陈丹琪分治算法，主要用于解决 维偏序问题。
前置知识
前置知识
- 树状数组
- 函数递归 / 分治
- 归并排序
偏序问题简述
维偏序，即有 个元素，每个元素有 个属性 ，求对于 ，使 且 的元素个数。
一维偏序问题
一维偏序，即给定 个整数，求对于数 ，满足 且 的整数个数。
可以考虑排序，复杂度 。
模板题：P1177@洛谷 - 【模板】快速排序。
二维偏序问题
二维偏序，在平面内有 个点，对于 ，求 ，此类问题可以考虑树状数组，复杂度 。
模板题：HDU1541@杭电 - Stars（由于很久以前做的忘记洛谷上那道题的题号了，只能从别人的博客找了外 OJ 的一道题。）
代码：懒得写了，引自[学习笔记]CDQ分治和整体二分
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=100000+10;
int n,c[maxn],ans[maxn];
struct Stars{
int x,y;
}a[maxn];
bool cmp(Stars a,Stars b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
void add(int x,int y){
for(;x<maxn;x+=lowbit(x)) c[x]+=y;
}
int sum(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=c[x];
return ans;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i].x=read(),a[i].y=read();
sort(a+1,a+n+1,cmp);
int now;
for(int i=1;i<=n;i++){
now=sum(a[i].y+1);
ans[now]++;
add(a[i].y+1,1);
}
for(int i=0;i<n;i++)
printf("%d\n",ans[i]);
return 0;
}
陈丹琪分治 - 三维偏序问题
简单来讲就只是在上面的二维偏序上面增加一个维度。
我们考虑按第一个属性排序，第二个属性使用归并排序，第三个属性使用树状数组。
归并排序时因为第一个属性有序，因此排序第二个属性时可以随意打乱，因为 。因为此时两个属性均有序，第三维就可以使用树状数组求解了，复杂度 。
模板题：P3810@洛谷 - 【模板】三维偏序（陌上花开）
以下是我的 AC 代码：（当时写的，码风可能不太好）
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
int n, m;
int ans[MAXN];
struct Node
{
int a, b, c;
int w, f;
bool operator < (const Node &p) const
{
if(a != p.a) return a < p.a;
if(b != p.b) return b < p.b;
return c < p.c;
}
}e[MAXN], tmp[MAXN];
namespace BIT
{
int index[MAXN<<1];
int lowbit(int x) {return x&(-x);}
void upd(int x, int y) {for(;x<=m;x+=lowbit(x)) index[x] += y;}
int sum(int x) {int ans = 0; for(;x;x-=lowbit(x)) ans += index[x]; return ans;}
}
namespace cdq
{
void mergesort(int l, int mid, int r)
{
int x = l, y = mid + 1, tot = l;
while(x <= mid && y <= r)
{
if(e[x].b <= e[y].b) BIT::upd(e[x].c, e[x].w), tmp[tot++] = e[x++];
else e[y].f += BIT::sum(e[y].c), tmp[tot++] = e[y++];
}
while(x <= mid) BIT::upd(e[x].c, e[x].w), tmp[tot++] = e[x++];
while(y <= r) e[y].f += BIT::sum(e[y].c), tmp[tot++] = e[y++];
for(int i=l;i<=mid;i++) BIT::upd(e[i].c, -e[i].w);
for(int i=l;i<=r;i++) e[i] = tmp[i];
}
void main(int l, int r)
{
int mid = (l + r) >> 1;
if(l == r) return;
main(l, mid);
main(mid+1, r);
mergesort(l, mid, r);
}
}
void de_weight(int &cnt)
{
sort(e+1, e+1+n);
cnt = 1;
for(int i=2;i<=n;i++)
{
if(e[i].a == e[cnt].a && e[i].b == e[cnt].b && e[i].c == e[cnt].c) ++e[cnt].w;
else e[++cnt] = e[i];
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>e[i].a>>e[i].b>>e[i].c;
e[i].w = 1;
e[i].f = 0;
}
int cnt;
de_weight(cnt);
cdq::main(1, cnt);
for(int i=1;i<=cnt;i++) ans[e[i].w+e[i].f-1] += e[i].w;
for(int i=0;i<n;i++) cout<<ans[i]<<endl;
return 0;
}
陈丹琪分治套陈丹琪分治 - 四维偏序问题
四维偏序问题也类似，需要陈丹琪分治套陈丹琪分治套树状数组。具体思想类似，在这里不详细讲了，复杂度 。
模板题：HDU5126@杭电 - Stars（没错这题也叫 Stars
代码：（还是引自上面那篇博客）
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=400000+10;
int n,m,mp[maxn],c[maxn],ans[maxn],tot;
struct Element{
int op,x,y,z,w,id,flag;
}e[maxn],t[maxn],d[maxn];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
void add(int x,int y){
for(;x<maxn;x+=lowbit(x)) c[x]+=y;
}
int sum(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=c[x];
return ans;
}
void CDQ3d(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
CDQ3d(l,mid);CDQ3d(mid+1,r);
int p=l,q=mid+1,cnt=l;
while(p<=mid&&q<=r){
if(t[p].y<=t[q].y){
if(t[p].op==1&&t[p].flag==0)
add(t[p].z,1);
d[cnt++]=t[p++];
}
else {
if(t[q].op==2&&t[q].flag==1)
ans[t[q].id]+=t[q].w*sum(t[q].z);
d[cnt++]=t[q++];
}
}
while(p<=mid){
if(t[p].op==1&&t[p].flag==0)
add(t[p].z,1);
d[cnt++]=t[p++];
}
while(q<=r){
if(t[q].op==2&&t[q].flag==1)
ans[t[q].id]+=t[q].w*sum(t[q].z);
d[cnt++]=t[q++];
}
for(int i=l;i<=mid;i++){
if(t[i].op==1&&t[i].flag==0)
add(t[i].z,-1);
}
for(int i=l;i<=r;i++) t[i]=d[i];
}
void CDQ2d(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
CDQ2d(l,mid);CDQ2d(mid+1,r);
int p=l,q=mid+1,cnt=l;
while(p<=mid&&q<=r){
if(e[p].x<=e[q].x){
t[cnt++]=e[p++];t[cnt-1].flag=0;
}
else {
t[cnt++]=e[q++];t[cnt-1].flag=1;
}
}
while(p<=mid){
t[cnt++]=e[p++];t[cnt-1].flag=0;
}
while(q<=r){
t[cnt++]=e[q++];t[cnt-1].flag=1;
}
for(int i=l;i<=r;i++) e[i]=t[i];
CDQ3d(l,r);
}
int main()
{
int T=read();
while(T--){
memset(ans,0,sizeof(ans));
m=read();tot=0;
int op,x1,y1,z1,x2,y2,z2,t=0;
for(int i=1;i<=m;i++){
op=read();
if(op==1){
x1=read(),y1=read(),z1=read();
e[++tot]=(Element){1,x1,y1,z1,1,tot,0};
}
else {
x1=read(),y1=read(),z1=read(),x2=read(),y2=read(),z2=read();
t++;
e[++tot]=(Element){2,x2,y2,z2,1,t,0};
e[++tot]=(Element){2,x1-1,y2,z2,-1,t,0};
e[++tot]=(Element){2,x2,y1-1,z2,-1,t,0};
e[++tot]=(Element){2,x2,y2,z1-1,-1,t,0};
e[++tot]=(Element){2,x1-1,y1-1,z2,1,t,0};
e[++tot]=(Element){2,x1-1,y2,z1-1,1,t,0};
e[++tot]=(Element){2,x2,y1-1,z1-1,1,t,0};
e[++tot]=(Element){2,x1-1,y1-1,z1-1,-1,t,0};
}
}
for(int i=1;i<=tot;i++) mp[i]=e[i].z;
sort(mp+1,mp+tot+1);
int cnt=unique(mp+1,mp+tot+1)-mp-1;
for(int i=1;i<=tot;i++) e[i].z=lower_bound(mp+1,mp+cnt+1,e[i].z)-mp;
CDQ2d(1,tot);
for(int i=1;i<=t;i++) printf("%d\n",ans[i]);
}
return 0;
}
高维偏序问题（）
在更高维的情况下陈丹琪分治也比较慢，基本就是暴力了。可以使用 bitset 优化，复杂度 ，这里不详细讲了。